A method of estimating the halftone dot frequencies in a band of an image by using a sliding window to segment the band into small areas, and keeping a running sum of the number of dots within the areas to calculate the dot frequency.
In order to perform various image processing functions such as segmentation, descreening, testing for halftone vs text, etc, it is often necessary to form a localized measure of image texture or dot frequency.
In a gray halftoned image the dots can simply be counted, but in shadows the dots are connected. A relatively simple texture function is described in FIG. 1 which will produce a value which is related to the total length of edges visible in a given region. These images were created by thresholding the L channel of Lab images of color and black and white halftoned regions. The lower images are small 15xc3x9715 windows cut from the centers of the upper images. Measurements of the texture using a previous method, which basically measures the total length of visible edges, results in very different values even though both are halftoned at 85 DPI.
Although valuable in general, this function produces different values when different gray levels are rendered at the same halftone frequency or halftoning is done in color rather than black and white. Other methods of estimating halftone frequencies such as collecting min/max separation lengths suffer from being less localized and relying on methods of finding peaks in histograms which can be difficult. A method that can run at high speeds and can be easily implemented is needed.
This method iteratively selects bands that can be the width of the image in the fast scan direction, but are a small number of scans in the process direction; for example, five scan lines. A window, 5 by 5 pixels in this example, can be positioned at the beginning of the band to define the first area, and the pixels in each column of the region are then processed iteratively. First the type of the current pixel is determined. Types frequently would be black or white, but any other attribute of the pixels could be used. If the current pixel is not the same type as the one above or to the left, it is assigned a new identification number. If it is the same as the one above or to the left it is assigned the same identification. If it is the same as the one above and to the left, the two original identifications are merged and one identification is used for all three. At the end of each column two numbers are determined. One is the number of separate identification numbers there are in the column. The other is the number of identifications that are in use in the entire image up to that column, which is the number of new identifications issued minus the number of merges.
Finally, to determine a value that is a function of the texture or dot frequency in the current area of the band bounded by the first and last column within the window, the process adds the number of identifications that were used in the left column of the area plus the number of identifications that are in use in the entire band up to the right column of the area minus the number of identifications that were used in the entire image up to the left column of the area. The resultant output is a number which is a function of the dot frequency of the area enclosed in the window and is associated with the central pixel of the area.
The window is then advanced one pixel to the right, the last column is again processed, and a new dot frequency is calculated and output as the value of the next central pixel of the window. The process is repeated until the right edge of the band is reached. The window is then reset to the left edge of the image and lowered by one pixel, and the next line of output pixels is produced. The total process therefore produces an output image having one output dot frequency pixel for each image input pixel. For 600 by 600 pixels and 85 halftone dots per inch, a typical patch is 15 by 15 pixels. A larger patch will be needed to measure a lower halftone frequency. This algorithm produces a good approximation of the dot frequency of an image and can be implemented easily in hardware.